#include "../include/backtracking.h"
#include <string.h>

/**
 * 计算当前解的上界（使用贪心思想）
 * @param items 物品数组
 * @param n 物品数量
 * @param capacity 背包容量
 * @param current_weight 当前已选物品的总重量
 * @param current_value 当前已选物品的总价值
 * @param level 当前处理到的物品索引
 * @return 上界值
 */
static double calculate_bound(Item* items, int n, int capacity,
                            double current_weight, double current_value, int level) {
    // 如果当前重量已经超过容量，返回0
    if (current_weight >= capacity) {
        return 0;
    }

    // 计算上界
    double bound = current_value;
    double remaining_capacity = capacity - current_weight;
    int i = level;

    // 贪心地选择剩余物品
    while (i < n && items[i].weight <= remaining_capacity) {
        bound += items[i].value;
        remaining_capacity -= items[i].weight;
        i++;
    }

    // 如果还有剩余容量，按比例添加最后一个物品的价值
    if (i < n) {
        bound += (remaining_capacity / items[i].weight) * items[i].value;
    }

    return bound;
}

/**
 * 回溯法求解0-1背包问题
 * 时间复杂度：O(2^n)，空间复杂度：O(n)
 * @param items 物品数组
 * @param n 物品数量
 * @param capacity 背包容量
 * @param result 结果结构体指针
 */
void backtracking_knapsack(Item* items, int n, int capacity, Result* result) {
    // 初始化结果
    result->total_value = 0;
    result->selected_count = 0;
    result->time_taken = 0;
    result->memory_used = 0;
    result->selected_items = NULL;

    // 记录开始时间
    clock_t start = clock();

    // 分配内存
    int* current_solution = (int*)calloc(n, sizeof(int));
    int* best_solution = (int*)calloc(n, sizeof(int));
    if (!current_solution || !best_solution) {
        printf("Memory allocation failed\n");
        free(current_solution);
        free(best_solution);
        return;
    }

    // 初始化变量
    double best_value = 0;
    double current_weight = 0;
    double current_value = 0;
    int level = 0;

    // 回溯过程
    while (level >= 0) {
        if (level == n) {
            // 到达叶子节点，更新最优解
            if (current_value > best_value) {
                best_value = current_value;
                memcpy(best_solution, current_solution, n * sizeof(int));
            }
            level--;
            continue;
        }

        // 尝试选择当前物品
        if (current_weight + items[level].weight <= capacity) {
            current_solution[level] = 1;
            current_weight += items[level].weight;
            current_value += items[level].value;
            level++;
        } else {
            // 计算上界
            double bound = calculate_bound(items, n, capacity,
                                        current_weight, current_value, level + 1);
            
            // 如果上界小于当前最优值，剪枝
            if (bound <= best_value) {
                level--;
            } else {
                // 不选择当前物品
                current_solution[level] = 0;
                level++;
            }
        }
    }

    // 记录结束时间和内存使用
    clock_t end = clock();
    result->time_taken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000;
    result->memory_used = n * sizeof(int) * 2;  // current_solution和best_solution数组

    // 保存结果
    result->total_value = best_value;
    result->selected_items = (int*)malloc(n * sizeof(int));
    if (result->selected_items) {
        for (int i = 0; i < n; ++i) {
            if (best_solution[i]) {
                result->selected_items[result->selected_count++] = items[i].id;
            }
        }
    }

    // 释放内存
    free(current_solution);
    free(best_solution);
} 